package com.yuufa;

import org.apache.commons.codec.digest.DigestUtils;
import org.apache.log4j.Logger;
import com.yuufa.node.TreeNode;

public class Yuufa {

    public static void main(String[] args) throws Exception {
        // fred.yang branch 測試
    }

    public static int[] getSpecificSource(int n) {
        int[] data = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            data[i] = (int) (Math.random() * 100);
        }

        return data;
    }

    public static int[] getSource(int n) {
        int[] data = new int[n];

        for (int i = 0; i < n; i++) {
            data[i] = (int) (Math.random() * 100);
        }

        return data;
    }
}

class Matrix {
    
    public static void test() {
        int n = 2 * 1 + 1;
        int[][] result = new int[n][n];
        int i = 0;
        int j = n / 2;

        for (int x = 0; x < n; x++) {
            for (int y = 0; y < n; y++) {
                result[x][y] = -1;
            }
        }

        result[i][j] = 1;

        for (int k = 2; k <= n * n; k++) {
            int q = ((i - 1 + n) % n);
            int w = ((j + 1) % n);

            if (result[q][w] != -1) {
                q = (i + 1) % n;
                w = j;
            }

            result[q][w] = k;
            i = q;
            j = w;
        }

        for (int x = 0; x < n; x++) {
            for (int y = 0; y < n; y++) {
                System.out.printf("%10d", result[x][y]);
            }
            System.out.println();
        }
    }
}

class Tree {
    
    public static void outputTree(TreeNode head) throws Exception {
        
    }
    
    public static int getMaxHeight(TreeNode head) throws Exception {
        
        if(head != null) {
            int leftHeight = getMaxHeight(head.getLeft());
            int rightHeight = getMaxHeight(head.getRight());
            
            if(leftHeight < rightHeight) {
                return rightHeight + 1;
            } else {
                return leftHeight + 1;
            }
        } else {
            return 0;
        }
    }
    
    public static void dfs(TreeNode head) throws Exception {
        
        Stack.push(head);
        
        while(!Stack.isEmpty()) {
            TreeNode ptr = Stack.pop();

            if(ptr != null) {
                System.out.print(ptr.getData() + "->");
                
                Stack.push(ptr.getLeft());
                Stack.push(ptr.getRight());
            }
            
        }
        
    }

    public static void bfs(TreeNode head) {
        // TODO breadth first search
        // by queue
    }

    public static void inorder(TreeNode head) {

        if (head != null) {
            inorder(head.getLeft());
            System.out.print(head.getData() + "->");
            inorder(head.getRight());
        }
    }

    public static TreeNode createBinaryTree(int n) {

        TreeNode head = new TreeNode();
        TreeNode pointer = head;
        head.setData((int) (Math.random() * 100));

        for (int i = 2; i <= n; i++) {
            head = pointer;
            int value = (int) (Math.random() * 100);

            TreeNode ptr = new TreeNode();
            ptr.setData(value);

            while (head != null) {
                if (value > head.getData()) {
                    if (head.getRight() != null) {
                        head = head.getRight();
                    } else {
                        head.setRight(ptr);
                        break;
                    }
                } else {
                    if (head.getLeft() != null) {
                        head = head.getLeft();
                    } else {
                        head.setLeft(ptr);
                        break;
                    }
                }
            }
        }

        return pointer;
    }
}

class DisjointSet {

    public static int[] makeset(int n) {

        int[] data = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            data[i] = i;
        }

        return data;
    }

    public static int find(int node, int[] data) {

        int j = node;

        while (data[j] != j) {
            j = data[j];
        }

        return j;
    }

    public static void merge(int p, int q, int[] data) {
        if (p < q) {
            data[q] = p;
        } else {
            data[p] = q;
        }
    }
}

class Queue {

    int n;
    int front;
    int rear;
    int[] q;

    public Queue(int n) {
        q = new int[n];
        front = 0;
        rear = 0;
        this.n = n;
    }

    public void enqueue(int v) throws Exception {
        if (((rear + 1) % n == front)) {
            throw new Exception("Queue is full");
        } else {
            rear = ++rear % n;
            q[rear] = v;
        }
    }

    public int dequeue() throws Exception {
        if (rear == front) {
            throw new Exception("Queue is empty");
        } else {
            front = ++front % n;
            return q[front];
        }
    }

}

class CircularQueue {
    public static final Logger log = Logger.getLogger(CircularQueue.class);

    static int n = 5;
    static int front = 0;
    static int rear = 0;
    static int[] q = new int[n];

    public static void enqueue(int v) throws Exception {
        if (((rear + 1) % n == front)) {
            throw new Exception("CircularQueue is full");
        } else {
            rear = ++rear % n;
            q[rear] = v;
        }
    }

    public static int dequeue() throws Exception {
        if (rear == front) {
            throw new Exception("CircularQueue is empty");
        } else {
            front = ++front % n;
            return q[front];
        }
    }

    public static void test() {
        int data;

        while (true) {
            int v = (int) (Math.random() * 2);

            try {
                if (v == 0) {
                    data = (int) (Math.random() * 100);
                    enqueue(data);
                    log.debug(String.format("enqueue:%d", data));
                } else {
                    data = dequeue();
                    log.debug(String.format("dequeue:%d", data));
                }
            } catch (Exception ex) {
                log.debug(ex);
            }
        }
    }
}

class LinearQueue {
    public static final Logger log = Logger.getLogger(LinearQueue.class);

    static int n = 5;
    static int front = -1;
    static int rear = -1;
    static int[] q = new int[n];

    public static void enqueue(int v) throws Exception {
        if (front == -1 && rear == (n - 1)) {
            throw new Exception("LinearQueue is full");
        } else if (front != -1 && rear == (n - 1)) {
            // LinearQueue not full but can't insert any record
            queueMove();
            q[++rear] = v;
        } else {
            q[++rear] = v;
        }
    }

    public static void queueMove() {
        
        for (int k = front + 1; k <= rear; k++) {
            q[k - front - 1] = q[k];
        }

        rear = rear - front - 1;
        front = -1;
    }

    public static int dequeue() throws Exception {
        if (front == rear) {
            throw new Exception("LinearQueue is empty");
        } else {
            return q[++front];
        }
    }

    public static void test() {
        int data;

        while (true) {
            int v = (int) (Math.random() * 2);

            try {
                if (v == 0) {
                    data = (int) (Math.random() * 100);
                    enqueue(data);
                    log.debug(String.format("enqueue:%d", data));
                } else {
                    data = dequeue();
                    log.debug(String.format("dequeue:%d", data));
                }
            } catch (Exception ex) {
                log.debug(ex);
            }
        }
    }
}

class Stack {
    public static final Logger log = Logger.getLogger(Stack.class);

    static int n = 10;
    static int sp = -1;
    static int[] s = new int[n];
    
    static int m = 10;
    static int msp = -1;
    static TreeNode[] node = new TreeNode[m];
    
    public static boolean isEmpty() throws Exception {
        return msp == -1;
    }
    
    public static void push(TreeNode v) throws Exception {
        if (msp == (m - 1)) {
            throw new Exception("stack is full");
        } else {
            node[++msp] = v;
        }
    }

    public static TreeNode pop() throws Exception {
        if (msp == -1) {
            throw new Exception("stack is empty");
        } else {
            return node[msp--];
        }
    }
/*
    public static void push(int v) throws Exception {
        if (sp == (n - 1)) {
            throw new Exception("stack is full");
        } else {
            s[++sp] = v;
        }
    }

    public static int pop() throws Exception {
        if (sp == -1) {
            throw new Exception("stack is empty");
        } else {
            return s[sp--];
        }
    }

    public static void test() {
        int data;

        while (true) {
            int v = (int) (Math.random() * 2);

            try {
                if (v == 0) {
                    data = (int) (Math.random() * 100);
                    log.debug(String.format("push:%d", data));
                    push(data);
                } else {
                    data = pop();
                    log.debug(String.format("pop:%d", data));
                }
            } catch (Exception ex) {
                log.debug(ex);
            }
        }
    }
*/
}

class ArrayMain {

    public static void test() {
        int n = 50;
        int[] data = new int[100];
        int digit = 1;

        data[1] = 1;

        for (int i = 1; i <= 50; i++) {

            for (int j = 1; j <= digit; j++) {
                data[j] = data[j] * i;
            }

            for (int j = 1; j <= digit; j++) {
                if (data[j] > 10) {
                    data[j + 1] += data[j] / 10;
                    data[j] = data[j] % 10;

                    if (j == digit) {
                        digit++;
                    }
                }
            }

            System.out.printf("%2d!=", i);
            for (int k = digit; k >= 1; k--) {
                System.out.print(data[k]);
            }
            System.out.println();
        }
    }
}

class Hanoi {

    public static void test() {
        int n = 4;
        move('a', 'b', 'c', n);
        System.out.println();
        loopMove('a', 'b', 'c', n);
    }

    public static void move(char a, char b, char c, int n) {
        if (n == 1) {
            System.out.print(String.format("%s->%s%s", a, c, ","));
        } else {
            move(a, c, b, n - 1);
            System.out.print(String.format("%s->%s%s", a, c, ","));
            move(b, a, c, n - 1);
        }
    }

    public static void loopMove(char a, char b, char c, int n) {
        int sp = -1;
        char[][] s = new char[1000][4];

        sp++;
        s[sp][0] = a;
        s[sp][1] = b;
        s[sp][2] = c;
        s[sp][3] = (char) n;

        while (sp != -1) {
            a = s[sp][0];
            b = s[sp][1];
            c = s[sp][2];
            n = s[sp][3];
            sp--;
            if (n == 1) {
                System.out.print(String.format("%s->%s%s", a, c, ","));
            } else {
                sp++;
                s[sp][0] = b;
                s[sp][1] = a;
                s[sp][2] = c;
                s[sp][3] = (char) (n - 1);
                sp++;
                s[sp][0] = a;
                s[sp][1] = b;
                s[sp][2] = c;
                s[sp][3] = 1;
                sp++;
                s[sp][0] = a;
                s[sp][1] = c;
                s[sp][2] = b;
                s[sp][3] = (char) (n - 1);
            }
        }
    }
}

class ReverseStr {

    public static void reverse(String str, int index) {
        if (index == (str.length() - 1)) {
            System.out.print(str.charAt(index));
        } else {
            reverse(str, index + 1);
            System.out.print(str.charAt(index));
        }
    }
}

class Travel {

    public static int[] createBinaryTree(int[] source, int n) {
        int[] dest = new int[2000];

        for (int i = 1; i <= dest.length - 1; i++) {
            dest[i] = -1;
        }

        dest[1] = source[1];

        for (int i = 2; i <= n; i++) {
            int tmp = source[i];
            int j = 1;

            while (dest[j] != -1) {
                if (tmp < dest[j]) {
                    j = j * 2;
                } else {
                    j = j * 2 + 1;
                }
            }

            dest[j] = tmp;
        }

        return dest;
    }

    public static void inorder(int[] source, int index) {

        if (source[index] != -1) {
            inorder(source, 2 * index);
            System.out.printf("%4d", source[index]);
            inorder(source, 2 * index + 1);
        }
    }
}

class Heap {

    public static void sort(int[] source, int n) {

        for (int i = n / 2; i >= 1; i--) {
            shift(source, i, n);
        }

        int tmp = source[1];
        source[1] = source[n];
        source[n] = tmp;

        for (int i = n - 1; i >= 2; i--) {
            shift(source, 1, i);

            tmp = source[1];
            source[1] = source[i];
            source[i] = tmp;
        }
    }

    public static void shift(int[] source, int i, int n) {
        int j = 2 * i;
        int tmp = source[i];

        while (j <= n) {
            if (j < n) {
                if (source[j] < source[j + 1]) {
                    j++;
                }
            }

            if (j <= n && tmp < source[j]) {
                source[j / 2] = source[j];
                j = j * 2;
            } else {
                break;
            }
        }

        source[j / 2] = tmp;
    }
}

class Shell {

    public static void sort(int[] source, int n) {
        for (int gap = n / 2; gap >= 1; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int tmp = source[i];
                int j = i - gap;
                while (j >= 0 && tmp < source[j]) {
                    source[j + gap] = source[j];
                    j -= gap;
                }
                source[j + gap] = tmp;
            }
        }
    }
}

class Insert {

    public static void sort(int[] source, int n) {

        for (int i = 1; i < n; i++) {
            int tmp = source[i];
            int j;
            for (j = i - 1; j >= 0 && tmp < source[j]; j--) {
                source[j + 1] = source[j];
            }
            source[j + 1] = tmp;
        }
    }
}

class TestString {

    public static int getStringIndexOf(String source, String target) {
        char[] sArray = source.toCharArray();
        int sLength = sArray.length;

        char[] tArray = target.toCharArray();
        int tLength = tArray.length;

        return indexOf(sArray, sLength, tArray, tLength);
    }

    public static int indexOf(char[] source, int sourceLength, char[] target, int targetLength) {
        char first = target[0];
        int max = sourceLength - targetLength;

        for (int i = 0; i <= max; i++) {
            if (first != source[i]) {
                while (++i <= max && first != source[i]);
            }

            if (i <= max) {
                int j = i + 1;
                int k = 1;
                for (k = 1; k < targetLength && source[j] == target[k]; j++, k++);
                if (k == targetLength) {
                    return i;
                }
            }
        }

        return -1;
    }
}

class NQueen {
    public static final Integer N = 4;
    public static final int[] queen = new int[N + 1];

    public static void queen(int i) {
        if (i == (N + 1)) {
            for (int k = 1; k <= N; k++) {
                System.out.printf("%4d", queen[k]);
            }
            System.out.println();
        } else {
            for (int j = 1; j <= N; j++) {
                queen[i] = j;
                if (promising(i)) {
                    queen(i + 1);
                }
            }
        }
    }

    public static boolean promising(int i) {

        for (int k = 1; k < i; k++) {
            if (queen[k] == queen[i] || (i - k) == Math.abs(queen[i] - queen[k])) {
                return false;
            }
        }

        return true;
    }
}

class Quick {

    public static void sort(int[] source, int left, int right, int n) {
        if (left < right) {
            int k = partition(source, left, right, n);
            sort(source, left, k - 1, n);
            sort(source, k + 1, right, n);
        }
    }

    public static int partition(int[] source, int left, int right, int n) {
        int pivot = source[left];
        int i = left;
        int j = right + 1;
        int tmp;

        while (true) {
            while (++i <= right && source[i] < pivot);
            while (--j >= left && source[j] > pivot);

            if (i < j) {
                tmp = source[i];
                source[i] = source[j];
                source[j] = tmp;
            } else {
                break;
            }
        }

        source[left] = source[j];
        source[j] = pivot;

        return j;
    }
}

class DepthFirst {
    public static int n = 8;
    public static int[][] matrix = new int[n + 1][n + 1];
    public static int[] visited = new int[n + 1];

    public static void dfs(int v) {
        visited[v] = 1;
        System.out.print(" ==> " + v);

        for (int i = 1; i <= n; i++) {
            if (matrix[v][i] == 1 && visited[i] == 0) {
                dfs(i);
            }
        }
    }

    public static void dfsUseStack(int v) {
        int[] s = new int[1000];
        int sp = 0;

        visited[v] = 1;
        System.out.print(" ==> " + v);
        s[++sp] = v;

        while (sp != 0) {
            int vertexNum = s[sp];
            int i;
            for (i = 1; i <= n; i++) {
                if (matrix[vertexNum][i] == 1 && visited[i] == 0) {
                    visited[i] = 1;
                    System.out.print(" ==> " + i);
                    s[++sp] = i;
                    break;
                }
            }

            if (i > n) {
                sp--;
            }
        }

    }

    public static void initial() {
        matrix[1][2] = 1;
        matrix[1][3] = 1;
        matrix[2][1] = 1;
        matrix[2][4] = 1;
        matrix[2][5] = 1;
        matrix[3][1] = 1;
        matrix[3][6] = 1;
        matrix[3][7] = 1;
        matrix[4][2] = 1;
        matrix[4][8] = 1;
        matrix[5][2] = 1;
        matrix[5][8] = 1;
        matrix[6][3] = 1;
        matrix[6][8] = 1;
        matrix[7][3] = 1;
        matrix[7][8] = 1;
        matrix[8][4] = 1;
        matrix[8][5] = 1;
        matrix[8][6] = 1;
        matrix[8][7] = 1;
    }
}